package com.uraurora.crescent.util;

import com.google.common.collect.Lists;
import com.google.common.collect.Queues;
import com.google.common.collect.Sets;
import com.sun.istack.internal.NotNull;

import java.util.*;
import java.util.function.Consumer;
import java.util.function.Function;
import java.util.function.Predicate;
import java.util.stream.Collectors;
import java.util.stream.Stream;

public final class Searcher<N> {

    private final Function<? super N, Collection<? extends N>> getSucceeding;

    private final Predicate<? super N> searcher;

    private static int MAX_THREAD_NUM = 20;

    private Searcher(Function<? super N, Collection<? extends N>> getSucceeding,
                     Predicate<? super N> searcher
    ){
        this.getSucceeding = getSucceeding;
        this.searcher = searcher;
    }

    private Searcher(){
        this.getSucceeding = null;
        this.searcher = null;
    }

    public static <N> Searcher<N> on(@NotNull Function<? super N, Collection<? extends N>> getSucceeding,
                                     @NotNull Predicate<? super N> searcher
    ){
        return new Searcher<>(
                Objects.requireNonNull(getSucceeding),
                Objects.requireNonNull(searcher)

        );
    }

    public static <N> Searcher<N> on(@NotNull Function<? super N, Collection<? extends N>> getSucceeding){
        return new Searcher<>(
                Objects.requireNonNull(getSucceeding),
                Searcher.ever()

        );
    }

    /**
     * 广度优先搜索
     * @param root 搜索的起点
     */
    public final List<N> bfs(N root){
        List<N> res = Lists.newLinkedList();
        bfsHelper(Collections.singletonList(root), res::add);
        return res;
    }

    /**
     * 起点有两个的广度优先搜索，使用{@code CountDonnLatch}实现同时开始搜索
     * @param start 搜索的第一个点
     * @param end 搜索的第二个点
     */
    public final List<N> bfs(N start, N end){
        List<N> res = Lists.newLinkedList();
        final Set<N> nodes = Stream.of(start, end).collect(Collectors.toSet());
        bfsHelper(nodes, res::add);
        return res;
    }

    public final List<N> bfs(N node1, N node2, N node3){
        List<N> res = Lists.newLinkedList();
        final Set<N> nodes = Stream.of(node1, node2, node3).collect(Collectors.toSet());
        bfsHelper(nodes, res::add);
        return res;
    }

    @SafeVarargs
    public final List<N> bfs(N node1, N node2, N node3,  N... nodes){
        List<N> res = Lists.newLinkedList();
        Set<N> nList = Sets.newHashSet(nodes);
        nList.addAll(Arrays.asList(node1, node2, node3));
        bfsHelper(nList, res::add);
        return res;
    }

    public final List<N> bfs(List<? extends N> nodes) {
        List<N> res = Lists.newLinkedList();
        bfsHelper(new HashSet<>(nodes), res::add);
        return res;
    }

    /**
     * 深度优先搜索
     * @param root 搜索的起点
     */
    public final List<N> dfs(N root){
        List<N> res = Lists.newLinkedList();
        dfsHelper(Collections.singletonList(root), res::add);
        return res;
    }

    public final List<N> dfs(N start, N end){
        List<N> res = Lists.newLinkedList();
        final Set<N> nodes = Stream.of(start, end).collect(Collectors.toSet());
        dfsHelper(nodes, res::add);
        return res;
    }

    public final List<N> dfs(N node1, N node2, N node3){
        List<N> res = Lists.newLinkedList();
        final Set<N> nodes = Stream.of(node1, node2, node3).collect(Collectors.toSet());
        dfsHelper(nodes, res::add);
        return res;
    }

    @SafeVarargs
    public final List<N> dfs(N node1, N node2, N node3,  N... nodes){
        List<N> res = Lists.newLinkedList();
        Set<N> nList = Sets.newHashSet(nodes);

        nList.addAll(Arrays.asList(node1, node2, node3));
        dfsHelper(nList, res::add);
        return res;
    }

    public final List<N> dfs(List<? extends N> nodes){
        List<N> res = Lists.newLinkedList();
        dfsHelper(new HashSet<>(nodes), res::add);
        return res;
    }

    /**
     * 拓扑排序
     * @param nodes
     * @return
     */
    public List<N> topSort(Collection<? extends N> nodes){
        assert getSucceeding != null;
        long size = nodes.stream().distinct().count();
        List<N> res = Lists.newLinkedList();
        Map<N, Integer> mapIndegree = getInDegree(nodes);
        List<N> filter = mapIndegree.entrySet().stream().filter(e->e.getValue()==0).
                map(Map.Entry::getKey).collect(Collectors.toList());
        if(filter.isEmpty()){return res;}

        Queue<N> queue = Queues.newArrayDeque(filter);

        Set<N> set = Sets.newHashSet();
        N currentNode;
        while(!queue.isEmpty()){
            currentNode = queue.poll();
            if (!set.contains(currentNode)) {
                res.add(currentNode);
            }
            set.add(currentNode);
            for(N node : getSucceeding.apply(currentNode)){
                Integer tmp = mapIndegree.get(node);
                tmp--;
                mapIndegree.put(node, tmp);
                if(!set.contains(node) && tmp==0){
                    queue.add(node);
                }
            }
        }
        if(res.size() != size){
            throw new IllegalArgumentException("the agrs must be a DAG,there is a circle including.");
        }
        return res;
    }


    /**
     * 在列表中搜索起点
     * @param nodes 节点集合
     * @return 起点列表
     */
    public List<N> searchStarts(Collection<? extends N> nodes){
        Set<N> set = nodes.stream().flatMap(node-> Objects.requireNonNull(getSucceeding).apply(node).stream()).collect(Collectors.toSet());
        return nodes.stream().filter(node->!set.contains(node)).collect(Collectors.toList());
    }

    /**
     * 搜索终点
     * @param nodes 节点集合
     * @return 终点列表
     */
    public List<N> searchEnds(Collection<? extends N> nodes){
        return nodes.stream().filter(node->isEnd(node, getSucceeding)).collect(Collectors.toList());
    }

    /**
     * 获取节点入度
     * @param nodes 节点集合
     * @return 入度map
     */
    public Map<N, Integer> getInDegree(Collection<? extends N> nodes){
        List<N> children = nodes.stream().distinct().flatMap(node->getSucceeding.apply(node).stream()).collect(Collectors.toList());
        return nodes.stream().collect(Collectors.toMap(
                node->node,
                node-> (int) children.stream().filter(n -> n.equals(node)).count(),
                (n1, n2) -> n2
        ));
    }

    /**
     * 获取节点出度
     * @param nodes 节点集合
     * @return 出度map
     */
    public Map<N, Integer> getOutDegree(Collection<? extends N> nodes){
        return nodes.stream().collect(Collectors.toMap(
                node -> node,
                node -> new HashSet<>(getSucceeding.apply(node)).size(),
                (n1, n2) -> n2,
                HashMap::new
        ));
    }

    /**
     * 深度迭代搜索（IDDFS）
     * @param root
     * @param searcher
     * @param depth
     * @return
     */
    public List<N> iterativeDeepeningDFS(Predicate<? super N> searcher,
                                         int depth,
                                         N root){
        List<N> res = Lists.newLinkedList();
        iterativeDeepeninDfsHelper(root, getSucceeding, searcher, 0,  depth, res);
        return res;
    }

    // TODO:搜索路径
    public List<N> searchPath(N  start, N end){
        return Lists.newLinkedList();
    }

    /**
     * 任意条件都满足
     * @param <N> 节点类型
     * @return always true
     */
    public static <N> Predicate<? super N> ever(){
        return node->true;
    }

    /**
     * 任意条件都不满足
     * @param <N> 节点类型
     * @return always false
     */
    public static <N> Predicate<? super N> never(){
        return node->false;
    }

    //<editor-fold desc="PRIVATE METHODS">

    /**
     * 通用BFS
     * @param nodes 搜索的起点集合
     */
    private void bfsHelper(Collection<? extends N> nodes, Consumer<? super N> action){
        Objects.requireNonNull(nodes).stream().filter(searcher).forEach(action);
        Set<N> set = new HashSet<>(nodes);
        Queue<N> queue = new ArrayDeque<>(nodes);
        N currentNode;

        while(!queue.isEmpty()){
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                currentNode = Objects.requireNonNull(queue.poll());
                for(N node : getSucceeding.apply(currentNode)){
                    if(!set.contains(node)){
                        queue.add(node);
                        if(searcher.test(node)){
                            action.accept(node);
                        }
                    }
                    set.add(node);
                }
            }
        }
    }

    /**
     * DFS通用函数
     * @param nodes 搜索的起点集合
     */
    private void dfsHelper(Collection<? extends N> nodes, Consumer<? super N> action){
        Objects.requireNonNull(nodes).stream().filter(searcher).forEach(action);
        Set<N> set = new HashSet<>(nodes);
        Deque<N> stack = new ArrayDeque<>(nodes);
        N currentNode;

        while(!stack.isEmpty()){
            currentNode = Objects.requireNonNull(stack.pollLast());
            if(!set.contains(currentNode) && searcher.test(currentNode)){
                action.accept(currentNode);
            }
            set.add(currentNode);
            for(N node : getSucceeding.apply(currentNode)){
                if(!set.contains(node)){
                    stack.addLast(node);
                }
            }
        }
    }

    /**
     * 深度迭代搜索（IDDFS）辅助
     * @param root
     * @param getSucceeding
     * @param searcher
     * @param depth
     * @param maxDepth
     * @param path
     * @param <N>
     */
    private static <N> void iterativeDeepeninDfsHelper(N root, Function<? super N, Collection<? extends N>> getSucceeding,
                                                       Predicate<? super N> searcher,
                                                       int depth, int maxDepth,
                                                       List<? super N> path){
        if(depth >= maxDepth){
            return;
        }
        if (searcher.test(root)) {
            path.add(root);
        }
        for(N node : getSucceeding.apply(root)){
            iterativeDeepeninDfsHelper(node, getSucceeding, searcher, ++depth, maxDepth, path);
        }
    }


    /**
     * 是否是终点（出度为0的节点）
     * @param node
     * @param getSucceeding
     * @param <N>
     * @return
     */
    private static <N> boolean isEnd(N node, Function<? super N, Collection<? extends N>> getSucceeding){
        return getSucceeding.apply(node).isEmpty();
    }
    //</editor-fold>


    // TODO:Astar

}
